import java.util.HashMap;

class Solution873 {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8};
        System.out.println(lenLongestFibSubseq(arr));
    }
    public static int lenLongestFibSubseq(int[] arr) {
       int n = arr.length ;
       // 记录每个元素, 对应的下标
        HashMap<Integer, Integer> hash = new HashMap<>() ;
        for(int i =0; i < n ; i ++){
            hash.put(arr[i] , i) ;
        }

        //状态表示 : dp[i][j] : 以 arr[i] 和 arr[j] 结尾的 最长斐波那契序列长度 ,  i < j
        // dp[i][j] 默认长度为 2 , 如果  arr[j] - arr[i] = k ,  k 存在 hash表里
        // 同时 k 的下标在 i 的前面 ==> k的下标 < i < j , 那么表示 dp[k下标][i] 的 后面可以 跟一个 j , 则 dp[k下标][i] ++
        // dp[k下标][i] + 1: 以 k 和 [i] 结尾的 最长斐波那契长度 + 1
        int[][] dp = new int[n][n];
        int max = 0 ;
        for(int i=0 ; i < n ; i ++){
            for(int j=0 ; j < n ; j ++){
               // 默认所有初始化为 2
                dp[i][j] = 2 ;
                if(i < j){   // i要在j前面
                 int k = arr[j] - arr[i] ;
                 // 如果k存在, 同时k的下标在 i 前面
                    if(hash.containsKey(k) && hash.get(k) < i) {
                        dp[i][j] = dp[hash.get(k)][i] + 1;  // 等于 k,i 结尾的子序列 加上 j
                    max = Math.max(max , dp[i][j]) ;
                    }
                }
            }
        }
        return max ;
    }
}